﻿#define _CRT_SECURE_NO_WARNINGS 1

// 小U和小R有两个字符串，分别是S和T现在小U需要通过对S进行若干次操作，使其变成T的一个前缀。
// 操作可以是修改S的某一个字符，或者删除S末尾的字符。现在你需要帮助小U计算出，
// 最少需要多少次操作才能让S变成T的前缀。

#include <iostream>
#include <string>
#include <vector>
#include <climits>
using namespace std;

int solution(string S, string T) {
    int s_len = S.size();
    int t_len = T.size();
    int n = min(s_len, t_len);
    vector<int> diff_counts(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        diff_counts[i] = diff_counts[i - 1] + (S[i - 1] != T[i - 1] ? 1 : 0);
    }

    int min_ops = INT_MAX;
    for (int m = 0; m <= n; ++m) {
        int modify = diff_counts[m];
        int del = s_len - m;
        int total = modify + del;
        if (total < min_ops) {
            min_ops = total;
        }
    }

    return min_ops;
}

int main() {
    cout << (solution("aba", "abb") == 1) << endl;
    cout << (solution("abcd", "efg") == 4) << endl;
    cout << (solution("xyz", "xy") == 1) << endl;
    cout << (solution("hello", "helloworld") == 0) << endl;
    cout << (solution("same", "same") == 0) << endl;
    return 0;
}